Given an integer arraynums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input:
 [-2,1,-3,4,-1,2,1,-5,4],

Output:
 6

Explanation:
 [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

class Solution {

public:

int maxSubArray\(vector<int>& nums\) {

    int result=nums\[0\];

    int dp\[nums.size\(\)\];

    dp\[0\]=nums\[0\];



    for \(int i=1;i<nums.size\(\);i++\){

       if \(\(dp\[i-1\]+nums\[i\]\)>=nums\[i\]\){

           dp\[i\]=dp\[i-1\]+nums\[i\];

       }

         else{

             dp\[i\]=nums\[i\];

         } 

        result=max\(result,dp\[i\]\);

      //cout<<dp\[i\]<<endl;

       }

    return result;

}

};